/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BASB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=MATH30/FONT#8=FIX25/FONT#9=GRKB30
␈↓ α∧␈↓␈↓ u1


␈↓ α∧␈↓α␈↓ ∧DTHE BLOB FUNCTIONS OF FLOW CHARTS

␈↓ α∧␈↓␈↓ αTWhen␈α
one␈αstudies␈α
programs␈α
organized␈αas␈α
flow␈α
charts,␈αone␈α
is␈α
inclined␈αto␈α
prefer␈α
flow␈αcharts
␈↓ α∧␈↓with␈αa␈αsingle␈αentry␈αand␈αa␈αsingle␈αexit.␈α However,␈αthe␈αoperations␈αof␈αbuilding␈αflow␈αcharts␈αfrom␈αparts
␈↓ α∧␈↓inevitably involve flow charts with multiple entries and multiple exits.

␈↓ α∧␈↓␈↓ αTOur␈α
approach␈αis␈α
to␈αcharacterize␈α
flow␈αcharts␈α
by␈αcertain␈α
functions,␈αcalled␈α
␈↓↓blob␈α
functions␈↓,␈αand
␈↓ α∧␈↓show␈αhow␈α
to␈αget␈α
the␈αfunctions␈α
characterizing␈αnew␈αflow␈α
charts␈αfrom␈α
those␈αcharacterizing␈α
the␈αflow
␈↓ α∧␈↓charts␈α
from␈α
which␈αthe␈α
new␈α
ones␈αare␈α
formed.␈α
 This␈α
is␈αin␈α
contrast␈α
with␈αthe␈α
approach␈α
of␈α
Ianov␈αas
␈↓ α∧␈↓described␈α⊂in␈α⊂(Ianov␈α⊂1959)␈α⊃and␈α⊂(Rutledge␈α⊂1964)␈α⊂who␈α⊂work␈α⊃directly␈α⊂with␈α⊂the␈α⊂flow␈α⊃charts.␈α⊂ Our
␈↓ α∧␈↓reason␈α∩is␈α⊃that␈α∩mathematics␈α⊃provides␈α∩us␈α⊃with␈α∩powerful␈α⊃tools␈α∩for␈α⊃manipulating␈α∩functions,␈α⊃and,
␈↓ α∧␈↓moreover,␈α
facts␈αabout␈α
flow␈α
charts␈αmust␈α
be␈α
combined␈αwith␈α
other␈α
mathematical␈αfacts␈α
which␈αare␈α
most
␈↓ α∧␈↓conveniently decribed in terms of functions, predicates and sets.










␈↓ α∧␈↓␈↓ εMFigure 1


␈↓ α∧␈↓α1. Blob functions

␈↓ α∧␈↓␈↓ αTFigure␈α1a␈αrepresents␈αa␈αflow␈αchart␈αor␈α␈↓↓blob␈↓␈α␈↓↓c␈↓␈αwhose␈αinner␈αworkings␈αwe␈αdo␈αnot␈αwish␈αto␈αspecify,
␈↓ α∧␈↓but␈α∂whose␈α⊂behavior␈α∂we␈α⊂wish␈α∂to␈α⊂characterize␈α∂by␈α∂functions.␈α⊂ The␈α∂arrows␈α⊂into␈α∂the␈α⊂␈↓↓blob␈↓␈α∂represent
␈↓ α∧␈↓paths␈α
along␈α
which␈αcontrol␈α
enters␈α
the␈α
flow␈αchart␈α
(called␈α
entries),␈α
and␈αthe␈α
arrows␈α
out␈αrepresent␈α
paths
␈↓ α∧␈↓by␈α
which␈α
control␈α
leaves␈α
it␈α(called␈α
␈↓↓exits).␈↓␈α
Let␈α
␈↓↓En(c)␈↓␈α
be␈αthe␈α
set␈α
of␈α
entries␈α
of␈α␈↓↓c,␈↓␈α
and␈α
let␈α
␈↓↓Ex(c)␈↓␈α
be␈αits␈α
set
␈↓ α∧␈↓of␈α⊃exits.␈α⊃ Let␈α⊃␈↓↓x␈↓␈α⊃represent␈α⊃the␈α⊃state␈α⊃vector,␈α⊃i.e.␈α⊃ the␈α⊃collection␈α⊃of␈α⊃assignments␈α⊃of␈α⊃values␈α∩to␈α⊃the
␈↓ α∧␈↓variables␈αoccurring␈α
in␈αthe␈α
program.␈α We␈α
define␈αpredicates␈α
␈↓↓p␈↓βij␈↓↓(x,c)␈↓␈αwhere␈α
␈↓↓i␈↓␈αranges␈α
over␈α␈↓↓En(c)␈↓␈αand␈α
␈↓↓j␈↓
␈↓ α∧␈↓ranges over ␈↓↓Ex(c)␈↓, and functions ␈↓↓s␈↓βi␈↓␈↓↓(x,c)␈↓ where ␈↓↓i␈↓ again ranges over ␈↓↓En(c)␈↓ as follows:

␈↓ α∧␈↓␈↓ αT(i)␈α
␈↓↓p␈↓βij␈↓␈↓↓(x,c)␈↓␈αis␈α
true␈αif␈α
and␈α
only␈αif␈α
entering␈αthe␈α
flow␈α
chart␈α␈↓↓c␈↓␈α
at␈αentry␈α
␈↓↓i␈↓␈α
with␈αinitial␈α
state␈α␈↓↓x␈↓␈α
results
␈↓ α∧␈↓in leaving the flow chart at exit ␈↓↓j␈↓.

␈↓ α∧␈↓␈↓ αT(ii)␈α␈↓↓s␈↓βi␈↓␈↓↓(x,c)␈↓␈α
is␈αthe␈αvalue␈α
of␈αthe␈αstate␈α
at␈αexit␈αfrom␈α
the␈αflow␈αchart␈α
when␈αit␈αis␈α
entered␈αat␈α
␈↓↓i␈↓␈αwith
␈↓ α∧␈↓initial state ␈↓↓x.␈↓ Note that the ␈↓↓s␈↓βi␈↓'s are partial functions, because the program may never exit.

␈↓ α∧␈↓␈↓ αTObviously␈α
the␈α
predicates␈α
␈↓↓p␈↓βij␈↓␈α∞and␈α
the␈α
functions␈α
␈↓↓s␈↓βi␈↓␈α
characterize␈α∞the␈α
flow␈α
chart␈α
␈↓↓c,␈↓␈α∞because␈α
if
␈↓ α∧␈↓one␈αknows␈αthese,␈αone␈αknows␈α
where␈αthe␈αprogram␈αwill␈αexit␈αand␈α
what␈αthe␈αnew␈αstate␈αwill␈αbe␈α
for␈αany
␈↓ α∧␈↓entrance into the flow chart.

␈↓ α∧␈↓␈↓ αTIf␈αwe␈αsuppose␈α
that␈αthe␈αflow␈αchart␈α
is␈αultimately␈αconstructed␈α
out␈αof␈αelementary␈αcompute␈α
blocks
␈↓ α∧␈↓and␈α
elementary␈αdecision␈α
blocks␈αas␈α
in␈αFigure␈α
1b,␈αone␈α
needs␈αto␈α
show␈αhow␈α
to␈αwrite␈α
the␈α␈↓↓p␈↓'s␈α
and␈α␈↓↓s␈↓'s␈α
for
␈↓ α∧␈↓these␈αelements␈αand␈α
then␈αhow␈αto␈α
get␈αthe␈α␈↓↓p␈↓'s␈α
and␈α␈↓↓s␈↓'s␈αfor␈α
a␈αcombination␈αof␈α
blocks␈αfrom␈αthose␈α
of␈αits
␈↓ α∧␈↓Flow Chart Functions␈↓ εd␈↓εDraft␈↓␈↓ u2


␈↓ α∧␈↓parts.␈α The␈αfirst␈αpart␈αis␈αtrivial.␈α A␈αcompute␈αblock␈αhas␈αjust␈αone␈αentry␈αand␈αone␈αexit,␈αso␈αthere␈αis␈αjust
␈↓ α∧␈↓one␈α⊂␈↓↓p␈↓␈α⊂and␈α⊂it␈α⊂is␈α⊂identically␈α⊂true,␈α⊂and␈α⊂there␈α⊂is␈α⊂just␈α⊂one␈α⊂␈↓↓s,␈↓␈α⊂and␈α⊂it␈α⊂is␈α⊂just␈α⊂the␈α⊂function␈α⊃of␈α⊂state
␈↓ α∧␈↓computed␈α
by␈αthe␈α
block.␈α A␈α
decision␈α
block␈αhas␈α
one␈αentry␈α
and␈αtwo␈α
exits␈α
and␈αthe␈α
one␈α␈↓↓p␈↓␈α
is␈α
just␈αthe
␈↓ α∧␈↓predicate␈αfor␈αthe␈αYES␈αdecision␈αand␈αthe␈αother␈αis␈αthe␈αpredicate␈αfor␈αthe␈αNO␈αdecision.␈α There␈αis␈αone
␈↓ α∧␈↓␈↓↓s,␈↓ and it is the identity function.
␈↓ α∧␈↓Flow Chart Functions␈↓ εd␈↓εDraft␈↓␈↓ u3


␈↓ α∧␈↓␈↓ αTWe introduce the following operations that give new charts from old ones:




















␈↓ α∧␈↓␈↓ εMFigure 2

␈↓ α∧␈↓␈↓ αT(i)␈α⊂Suppression␈α⊂of␈α⊂an␈α⊃entry␈α⊂␈↓↓i␈↓β0␈↓␈α⊂from␈α⊂a␈α⊃chart␈α⊂␈↓↓c␈α⊂(see␈↓␈α⊂Figure␈α⊃2a).␈α⊂ This␈α⊂gives␈α⊂a␈α⊃new␈α⊂chart
␈↓ α∧␈↓␈↓↓suppress(c,i␈↓β0␈↓↓)␈↓␈αwith␈αone␈αfewer␈αentry,␈αand␈αwhose␈α␈↓↓p␈↓'s␈αand␈α␈↓↓s␈↓'s␈αare␈αthe␈αsame␈αas␈αbefore␈αexcept␈αthat␈αthe
␈↓ α∧␈↓subscript ␈↓↓i␈↓β0␈↓ is omitted.

␈↓ α∧␈↓␈↓ αT(ii)␈α⊃Adjoining␈α∩two␈α⊃charts␈α∩␈↓↓c1␈↓␈α⊃and␈α∩␈↓↓c2␈↓␈α⊃side␈α⊃by␈α∩side␈α⊃(see␈α∩Figure␈α⊃2b).␈α∩ Call␈α⊃the␈α∩new␈α⊃chart
␈↓ α∧␈↓␈↓↓adjoin(c1,c2)␈↓.␈α⊂ We␈α⊂have␈α⊂␈↓↓En(adjoin(c1,c2))␈α⊂=␈α⊃En(c1)␈α⊂∪␈α⊂En(c2)␈↓,␈α⊂and␈α⊂␈↓↓Ex(adjoin(c1,c2))␈α⊂=␈α⊃Ex(c1)␈α⊂∪
␈↓ α∧␈↓↓Ex(c2)␈↓.  Moreover, we have

␈↓ α∧␈↓1)␈↓ αt␈α␈↓↓p␈↓βij␈↓↓(x,adjoin(c1,c2))␈α=␈α␈↓αif␈↓↓␈αi␈αε␈αc1␈α␈↓αthen␈↓↓␈α(␈↓αif␈↓↓␈αj␈αε␈αc1␈α␈↓αthen␈↓↓␈αp␈↓βij␈↓↓(x,c1)␈α␈↓αelse␈↓↓␈α␈↓αfalse␈↓↓)␈α␈↓αelse␈↓↓␈α(␈↓αif␈↓↓␈αj␈αε␈αc1␈α␈↓αthen␈↓↓
␈↓ α∧␈↓↓␈↓αfalse␈↓↓ ␈↓αelse␈↓↓ p␈↓βij␈↓↓(x,c2))␈↓,

␈↓ α∧␈↓and

␈↓ α∧␈↓2)␈↓ αt ␈↓↓s␈↓βi␈↓↓(x,adjoin(c1,c2)) = ␈↓αif␈↓↓ i ε c1 ␈↓αthen␈↓↓ s␈↓βi␈↓↓(x,c1) ␈↓αelse␈↓↓ s␈↓βi␈↓↓(x,c2)␈↓.

␈↓ α∧␈↓Both of these are trivial operations but the next is not.

␈↓ α∧␈↓␈↓ αT(iii)␈α
Connecting␈α∞the␈α
exit␈α
␈↓↓m␈↓␈α∞to␈α
the␈α∞entry␈α
␈↓↓n␈↓␈α
giving␈α∞a␈α
new␈α
chart␈α∞␈↓↓loop(c,m,n)␈↓␈α
with␈α∞one␈α
fewer
␈↓ α∧␈↓exit (see Figure 2c).  The new ␈↓↓p␈↓'s and ␈↓↓s␈↓'s are defined by the recursion equations

␈↓ α∧␈↓3)␈↓ αt ␈↓↓p␈↓βij␈↓↓(x,loop(c,m,n)) ← p␈↓βij␈↓↓(x,c) ∨ (p␈↓βim␈↓↓(x,c) ∧ p␈↓βnj␈↓↓(s␈↓βi␈↓↓(x,c),loop(c,m,n)))␈↓

␈↓ α∧␈↓and

␈↓ α∧␈↓4)␈↓ αt ␈↓↓s␈↓βi␈↓↓(x,loop(c,m,n)) ← ␈↓αif␈↓↓ ¬p␈↓βim␈↓↓(x,c) ␈↓αthen␈↓↓ s␈↓βi␈↓↓(x,c) ␈↓αelse␈↓↓ s␈↓βn␈↓↓(s␈↓βi␈↓↓(x,c),loop(c,m,n))␈↓.
␈↓ α∧␈↓Flow Chart Functions␈↓ εd␈↓εDraft␈↓␈↓ u4


␈↓ α∧␈↓␈↓ αTA␈αlittle␈αcontemplation␈αwill␈αshow␈αthat␈αthis␈αrecursive␈αprocess␈αcaptures␈αour␈αintuitive␈α
notion␈αof
␈↓ α∧␈↓what happens when an exit is connected to an entry.

␈↓ α∧␈↓␈↓ αTIt␈αis␈αevident␈αthat␈αany␈αflow␈αchart␈α
can␈αbe␈αbuilt␈αfrom␈αelementary␈αcompute␈αblocks␈αand␈α
tests␈αby
␈↓ α∧␈↓these␈α∃operations,␈α∀and␈α∃furthermore␈α∃any␈α∀two␈α∃flow␈α∀charts␈α∃can␈α∃be␈α∀glued␈α∃together␈α∃using␈α∀these
␈↓ α∧␈↓operations.

␈↓ α∧␈↓␈↓ αTAn␈α⊂objective␈α∂worth␈α⊂undertaking␈α⊂is␈α∂to␈α⊂show␈α⊂that␈α∂any␈α⊂two␈α⊂equivalent␈α∂flow␈α⊂charts␈α⊂can␈α∂be
␈↓ α∧␈↓proved␈α∂equivalent␈α∂by␈α⊂the␈α∂theory␈α∂of␈α∂recursively␈α⊂defined␈α∂functions␈α∂from␈α∂these␈α⊂definitions.␈α∂ This
␈↓ α∧␈↓would␈α⊂be␈α⊂the␈α⊂analog␈α⊂of␈α⊃Ianov's␈α⊂theorem␈α⊂and␈α⊂ought␈α⊂to␈α⊃be␈α⊂based␈α⊂on␈α⊂a␈α⊂decision␈α⊃procedure␈α⊂for
␈↓ α∧␈↓recursions␈α
(possibly␈α
restricted␈αto␈α
iterative␈α
form)␈α
where␈αthere␈α
is␈α
only␈αone␈α
variable.␈α
 It␈α
would␈αhave
␈↓ α∧␈↓the␈αadvantage␈αover␈αthe␈αIanov␈αtheory␈αthat␈αit␈α
is␈αsimply␈αthe␈αtheory␈αof␈αrecursion␈αequations␈αapplied␈α
to
␈↓ α∧␈↓this case rather than an ad hoc confection.

␈↓ α∧␈↓␈↓ αTI␈α
don't␈α
know␈α
such␈α
a␈α
decision␈α
procedure,␈αnor␈α
has␈α
there␈α
been␈α
formulated␈α
a␈α
theory␈αof␈α
recursion
␈↓ α∧␈↓equations that is proved complete for this case.

␈↓ α∧␈↓Note of February 19, 1977:

␈↓ α∧␈↓␈↓ αTThe␈α⊂recursion␈α∂involved␈α⊂when␈α∂an␈α⊂exit␈α∂is␈α⊂connected␈α∂to␈α⊂an␈α∂entry␈α⊂can␈α∂be␈α⊂represented␈α⊂by␈α∂a
␈↓ α∧␈↓␈↓↓functional␈α⊃equation␈↓␈α⊃and␈α⊃a␈α⊃␈↓↓minimization␈α⊃schema␈↓␈α⊃as␈α⊃discussed␈α⊃in␈α⊃(McCarthy␈α⊃1977).␈α⊃ The␈α⊃file␈α⊂is
␈↓ α∧␈↓FIRST.NEW[W77,JMC],␈α∪REPRESENTATION␈α∀OF␈α∪RECURSIVE␈α∪PROGRAMS␈α∀IN␈α∪FIRST
␈↓ α∧␈↓ORDER␈α⊃LOGIC.␈α⊃ Most␈α⊂likely␈α⊃this␈α⊃is␈α⊂sufficient␈α⊃information␈α⊃to␈α⊂prove␈α⊃equivalence␈α⊃of␈α⊃the␈α⊂two
␈↓ α∧␈↓flowcharts by first order logic alone.

␈↓ α∧␈↓␈↓ αTIf␈αtwo␈αexits␈αof␈αa␈αchart␈αare␈αconnected␈αto␈αtwo␈αentries,␈αthis␈αcan␈αbe␈αdone␈αin␈αtwo␈αdifferent␈α
orders
␈↓ α∧␈↓-␈αthus␈αgiving␈αrise␈αto␈αtwo␈αsets␈αof␈αrecursions␈αfor␈αthe␈αnew␈αchart.␈α Moreover,␈αa␈αthird␈αset␈αof␈αrecursions
␈↓ α∧␈↓can␈αbe␈αobtained␈αby␈αdoing␈αthe␈αconnections␈αsimultaneously.␈α It␈αshould␈αbe␈αpossible␈αto␈αshow␈αfrom␈αthe
␈↓ α∧␈↓␈↓↓functional␈α⊂equations␈↓␈α⊂and␈α⊂␈↓↓minimization␈α⊂schemas␈↓␈α⊂of␈α∂these␈α⊂recursions␈α⊂that␈α⊂the␈α⊂same␈α⊂functions␈α∂are
␈↓ α∧␈↓obtained.




␈↓ α∧␈↓αREFERENCES

␈↓ α∧␈↓␈↓αIanov,␈α
Y.I.␈↓␈α
(1960):␈α
"The␈α
Logical␈α
Schemes␈α
of␈α
Algorithms",␈α
in␈α
␈↓↓␈α
Problems␈α
of␈α
Cybernetics␈↓,␈α
vol.1,␈αpp.␈α
82-
␈↓ α∧␈↓140, Pergamon Press, New York (English Translation).

␈↓ α∧␈↓␈↓αRutledge, J.D.␈↓ (1964): "On Ianov's Program Schemata", ␈↓↓J. ACM␈↓, ␈↓α11␈↓(1): 1-9 (January).


␈↓ α∧␈↓John McCarthy
␈↓ α∧␈↓Artificial Intelligence Laboratory
␈↓ α∧␈↓Computer Science Department
␈↓ α∧␈↓Stanford University
␈↓ α∧␈↓Stanford, California 94305

␈↓ α∧␈↓ARPANET: MCCARTHY@SU-AI
␈↓ α∧␈↓Flow Chart Functions␈↓ εd␈↓εDraft␈↓␈↓ u5


␈↓ α∧␈↓␈↓εThis draft of BLOB[W76,JMC] PUBbed at 11:36 on August 6, 1979.␈↓